Codeforces Round #110 (Div. 2)

A

弱智题，统计一下每行每列的和即可。

时间复杂度 $O(n^2)$ 。

Code

#include <cstdio>

const int N = 35;

int a[N][N], row[N], col[N], n, res;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
            row[i] += a[i][j];
            col[j] += a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            if (col[j] > row[i]) res++;
    }
    printf("%d\n", res);
}

B

对半径从大到小排序，顺次模拟即可。

时间复杂度 $O(n\log{n})$ 。

Code

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 1e5 + 5;
const double pi = acos(-1);

double r[N], res;

int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lf", &r[i]);
    sort(r + 1, r + n + 1);
    reverse(r + 1, r + n + 1);
    for (int i = 1; i <= n; i++) {
        if (i & 1) res += pi * r[i] * r[i];
        else res -= pi * r[i] * r[i];
    }
    printf("%.10lf\n", res);
}

C

由于插入和删除都是在头尾进行的，可以枚举 $b$ 的左端点在 $a$ 中的位置，暴力匹配即可。

时间复杂度 $O(nm)$ 。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 2005;

char a[N], b[N];

int main() {
    scanf("%s%s", a + 1, b + 1);
    int n = strlen(a + 1);
    int m = strlen(b + 1);
    int ans = m;
    for (int i = -m; i <= n; i++) {
        int res = m;
        for (int j = 1; j <= m; j++) {
            if (i + j <= 0 || i + j >= n + 1) continue;
            if (a[i + j] == b[j]) res--;
        }
        ans = min(ans, res);
    }
    printf("%d\n", ans);
}

D

有趣的推理题。

对于每一个人，设 $T_i$ 为指控这个人是罪犯的人数，$F_i$ 为指控这个人不是罪犯的人数。

先假设所有人都不是罪犯，处理出来 $T_i$ 与 $F_i$ 的值，同时记录 $n$ 句话中真话数量 $s$ 。

然后我们让每个人尝试成为罪犯。如果 $i$ 成为罪犯，那么 $T_i$ 和 $F_i$ 将会互换。原本 $s$ 句真话中有 $F_i$ 句会变为假话，$T_i$ 句变为真话。

而一共有 $m$ 句真话，所以当且仅当
$s + T_i - F_i = m$ 时 $i$ 才有可能成为罪犯。我们记录下来可能成为罪犯的人以及可能成为罪犯的人数。

然后就可以输出了。对于第 $i$ 句话，判断一下这句话指控的人是否可能为罪犯以及罪犯人数即可。

时间复杂度 $O(n)$ 。

Code

#include <cstdio>

const int N = 1e5 + 5;

int n, m, s, cnt, a[N], sus[N], con[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if (a[i] > 0) con[a[i]]++;
        else con[-a[i]]--, s++;
    }
    for (int i = 1; i <= n; i++)
        if (con[i] + s == m) {
            cnt++;
            sus[i] = 1;
        }
    for (int i = 1; i <= n; i++) {
        if (a[i] > 0) {
            if (!sus[a[i]]) puts("Lie");
            else if (cnt == 1) puts("Truth");
            else puts("Not defined");
        } else {
            if (!sus[-a[i]]) puts("Truth");
            else if (cnt == 1) puts("Lie");
            else puts("Not defined");
        }
    }
}

E

我们将字符 $\texttt{a}$ 到 $\texttt{z}$ 对应为 $1$ 至 $26$ ，容易发现每一次操作整个串的和是不变的。

由于操作可以传递，变换相邻字符的操作可以经过若干次操作变成变换任意两个字符。于是问题就变成了给定总和求字符串个数。

很显然的dp。设 $f_{i,\,j}$ 为字符串 $s$ 的前 $i$ 位和为 $j$ 的总数。转移方程显然

$f_{i,\,j}=\sum\limits_{k=1}^{\min\{j,26\}}f_{i-1,\,j-k}$

由于多组数据，我们可以先预处理 $f_{i,\,j}$ ，询问直接输出即可。

时间复杂度 $O(26^2n^2)$ 。

Code

#include <algorithm>
#include <cstdio>
using namespace std;

const int N = 105;
const int mod = 1e9 + 7;

int f[N][N * 26], n, sum, T;
char s[N];

int main() {
    f[0][0] = 1;
    for (int i = 1; i <= 100; i++) {
        for (int j = 1; j <= 2600; j++)
            for (int k = 1; k <= min(j, 26); k++)
                f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;
    }
    scanf("%d", &T);
    while (T--) {
        scanf("%s", s);
        sum = 0;
        n = strlen(s);
        for (int i = 0; i < n; i++) sum += s[i] - 'a' + 1;
        printf("%d\n", f[n][sum] - 1);
    }
}